package com.cuz.series.linklist;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/***
 * 23. 合并K个升序链表 https://leetcode.cn/problems/swap-nodes-in-pairs/
 */
public class 链表9合并k个升序链表 {


    public static ListNode mergeKLists1(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    public static ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(l -> l.val));
        for (ListNode loop : lists) {
            q.add(loop);
        }
        ListNode preHead = new ListNode();
        ListNode tail = preHead;
        while (!q.isEmpty()) {
            ListNode poll = q.poll();
            tail.next = poll;
            if (poll.next != null) {
                q.add(poll.next);
                poll.next = poll.next.next;
            }
            tail=tail.next;
        }
        return preHead.next;
    }

    private static ListNode merge(ListNode[] arr, int l, int r) {
        if (l == r) {
            return arr[l];
        }
        if (l + 1 == r) {
            return mergeTwoLists1(arr[l], arr[r]);
        }
        int mid = (l + r) / 2;
        return mergeTwoLists1(merge(arr, l, mid), merge(arr, mid + 1, r));
    }

    public static ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode preHead = new ListNode();
        ListNode tail = preHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = unlinkReturnNext(list1);
            } else {
                tail.next = list2;
                list2 = unlinkReturnNext(list2);
            }
            tail = tail.next;
        }
        tail.next = list1 == null ? list2 : list1;
        return preHead.next;
    }

    private static ListNode unlinkReturnNext(ListNode node) {
        ListNode next = node.next;
        node.next = null;
        return next;
    }


}
